#include <iostream>
#include <vector>
#include <numeric>
#include "euler.h"

BEGIN_PROBLEM(101, solve_problem_101)
	PROBLEM_TITLE("Polynomial fitting of the initial terms of a given sequence")
	PROBLEM_ANSWER("37076114526")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("n^3")
	PROBLEM_SPACE_COMPLEXITY("n")
	PROBLEM_KEYWORDS("curve fitting")
END_PROBLEM()

// @timecomplexity: O(n^2)
// @spacecomplexity: O(n)
template <typename Iter>
typename Iter::value_type next_in_sequence(Iter first, Iter last)
{
	typedef typename Iter::value_type T;

	// Diff the sequence until there is only one item.
	std::vector<T> seq(first, last);
	for (size_t i = seq.size() - 1; i >= 1; --i)
	{
		// in-place first difference.
		for (size_t j = 0; j < i; j++)
			seq[j] = seq[j+1] - seq[j];
	}

	// Computes the next term.
	return std::accumulate(seq.cbegin(), seq.cend(), T(0));
}

static void solve_problem_101()
{
#if 0
	const int ORDER = 3;
	typedef int value_t;
	auto u = [](int n) -> value_t { return n*n*n; };
#else
	const int ORDER = 10;
	typedef long long value_t;
	auto u = [](int n) -> value_t {
		value_t y = 0;
		for (int i = 0; i <= 10; i++)
			y = 1 - n * y;
		return y;
	};
#endif

	bool verbose = false;

	// Display the true polynomial.
	std::vector<value_t> y(ORDER);
	for (int i = 0; i < ORDER; i++)
	{
		y[i] = u(i+1);
		if (verbose)
			std::cout << "u(" << (i+1) << ") = " << y[i] << std::endl;
	}

	// Fit 1 to 10 terms, and find the sum of First-Incorrect-Term.
	value_t total_incorrect = 0;
	for (int terms = 1; terms <= ORDER; terms++)
	{
		value_t fit = next_in_sequence(y.cbegin(), y.cbegin() + terms);
		total_incorrect += fit;
	}
	std::cout << total_incorrect << std::endl;
}
